Baraj pentru lotul olimpic, Bucuresti, mai 1997
Problema 4 (Distribuitoare)  - Iuliu Vasilescu
Dificultate: C4

	Un distribuitor de bile este un aparat cu o intrare si doua iesiri
(una stanga si una dreapta) care functioneaza astfel: pe intrare primeste un sir
de bile pe care le distribuie alternativ prin cele doua iesiri. Deci, prima bila
iese prin stanga, a doua prin dreapta, a treia prin stanga...
	Sa consideram acum un arbore format din astfel de distribuitoare. Intr-un 
astfel  de arbore bilele se introduc prin varful arborelui si trec succesiv prin 
distribuitoare in functie de starea fiecarui distribuitor, pana ajung la o 
iesire care nu este conectata la nici un distribuitor; spunem ca atunci au parasit
arborele. Daca iesirea pe care au parasit arborele era iesirea din stanga a unui
distribuitor, atunci se spune ca au parasit arborele prin stanga; analog pentru
celalalt caz.
	Vom considera in continuare un aparat format dintr-un astfel de arbore 
si sub el o tavita cu N bile, numerotate de la 1 la N, asezate initial in ordine
crescatoare de la stanga la dreapta. Cum functioneaza un astfel de aparat ?
La fiecare pas toate bilele sunt luate din tavita si introduse in arbore, in ordinea
in care erau in tavita, de la stanga la dreapta. Fiecare bila care va parasi 
arborele prin stanga se va aseza in tavita in stanga bilelor deja existente in
tavita in momentul caderii ei, si analog, fiecare bila care va p[arasi arborele
prin partea dreapta se va aseza in dreapta bilelor. O bila este introdusa in arbore
doar dupa ce predecesoarea sa a ajuns deja in tavita. Dupa un astfel de pas din
nou toate bilele se vor afla in tavita, dar in alta ordine. 
	Pentru o configuratie data, sa se calculeze numarul minim  de pasi dupa
care bilele ajung in tavita in ordinea initiala.
Observatie: dupa fiecare pas distribuitoarele sunt "resetate" astfel incat prima
bila pe care o vor primi din pasul urmator o vor arunca prin stanga.
Intrare: fisierul INPUT.4 are urmatoarea structura:
n m		- n = numarul de bile, m = numarul de distribuitoare (1<=n,m<=1000)
Ai Bi Ci	- pe fiecare astfel de linie (pana la sfarsitul fisierului) se
........	  gasesc 3 numere cu semnificatia ca Bi se afla conectat la iesirea
		  stanga a lui Ai, iar Ci la iesirea dreapta a lui Ai.
		  Daca Ci sau Bi sunt 0, inseamna ca la iesirea corepunzatoare
		  nu se afla conectata alta intrare.
		  In varf se afla totdeauna distribuitorul 1.
Iesire: fisierul OUTPUT.4 va contine o singura linie, cu numarul de pasi.
Exemplu:
INPUT.4
4 4
1 2 3
3 4 0
OUTPUT.4
2
============================
Solutie (Iuliu Vasilescu)
program mirela;
const nmax=1005;
      lmax=1005;
type numar=array[1..nmax] of byte;
     vector=array[1..lmax] of integer;
var a,b,c,d,g,h:vector;
    i,j,n,m,lm,k,l:integer;
    f:text;
    nr,add:longint;
    adda,nra:numar;
procedure suma(var a,b,c:numar);
var i,k:integer;
begin
    k:=0;
    for i:=1 to nmax do begin
        k:=k+a[i]+b[i];
        c[i]:=k mod 10;
        k:=k div 10;
    end;
end;

procedure afis(var a:numar);
var i,k:integer;
begin
    k:=0;
    for i:=1 to nmax do if a[i]<>0 then k:=i;
    for i:= k downto 1 do write(a[i]);
end;
procedure insert(var a:vector;c:integer;p:byte);
var i,k:integer;
begin
    if p=0 then begin
        for i:=1 to lmax do begin
            k:=a[i];a[i]:=c;c:=k;
        end;
    end else begin
        k:=1;
        while a[k]<>0 do inc(k);
        a[k]:=c;
    end;
end;

procedure compune(var a,b,c:vector);
var i:integer;d:vector;
begin
   for i:=1 to n do begin
       d[i]:=a[b[i]];
   end;
   c:=d;
end;

function corect(var a:vector):boolean;
var i:integer;r:boolean;
begin
    r:=true;
    for i:=1 to n do if a[i]<>i then begin
       i:=n;r:=false;
    end;
    corect:=r;
end;

function maicorect(var a,b:vector):boolean;
var i:integer;r:boolean;
begin
    r:=false;
    for i:=1 to n do if (a[i]<>i)and(b[i]=i) then begin
       i:=n;r:=true;
    end;
    maicorect:=r;
end;
var s:string;
begin
     for i:=1 to lmax do begin
         a[i]:=0;b[i]:=0;c[i]:=0;d[i]:=0;
     end;
     write('fisier=');
     readln(s);
     assign(f,s);reset(f);
     readln(f,n,m);
     lm:=0;
     while not seekeof(f) do begin
        read(f,k);
        readln(f,g[k],h[k]);
        inc(lm);
     end;
     close(f);
     while(n<>0) do begin
         for i:=1 to lmax do begin
             a[i]:=0;d[i]:=0;
         end;
         b:=g;c:=h;
         for i:=1 to n do begin
             k:=1;l:=d[1];
             while ((d[k]=0)and(b[k]<>0))or((d[k]=1)and(c[k]<>0)) do begin
                 if d[k]=0 then j:=b[k] else j:=c[k];
                 d[k]:=(d[k]+1)mod 2;
                 k:=j;
             end;
             insert(a,i,d[k]);
             d[k]:=(d[k]+1)mod 2;
         end;
         b:=a;add:=1;nr:=1;
         for i:=1 to nmax do begin adda[i]:=0;nra[i]:=0;end;
         adda[1]:=1;nra[1]:=1;
         while not corect(b) do begin
             compune(a,b,b);
             inc(nr,add);
             suma(adda,nra,nra);
             if maicorect(a,b) then begin
                add:=nr;
                adda:=nra;
                a:=b;
             end;
             if nr>1000000000 then begin
                 writeln('Number too long');
             end;
         end;
         writeln('gugu:',nr);
         write('Corect:');afis(nra);writeln;
         readln;
         n:=0;
     end;
end.
================================
	TESTE
Intrare:

test 1:
4 4
1 2 3
3 4 0
--------------------
test 2:
1 6
1 2 3
3 4 5
2 0 6
----------------------
test 3:
928 6
1 2 3
3 4 5
2 0 6
---------------------
test 4:
89 6
1 2 3
3 4 5
2 0 6
---------------------
test 5:
876 255
1 2 3
2 4 5
3 6 7
4 8 9
5 10 11
6 12 13
7 14 15
8 16 17
9 18 19
10 20 21
11 22 23
12 24 25
13 26 27
14 28 29
15 30 31
16 32 33
17 34 35
18 36 37
19 38 39
20 40 41
21 42 43
22 44 45
23 46 47
24 48 49
25 50 51
26 52 53
27 54 55
28 56 57
29 58 59
30 60 61
31 62 63
32 64 65
33 66 67
34 68 69
35 70 71
36 72 73
37 74 75
38 76 77
39 78 79
40 80 81
41 82 83
42 84 85
43 86 87
44 88 89
45 90 91
46 92 93
47 94 95
48 96 97
49 98 99
50 100 101
51 102 103
52 104 105
53 106 107
54 108 109
55 110 111
56 112 113
57 114 115
58 116 117
59 118 119
60 120 121
61 122 123
62 124 125
63 126 127
64 128 129
65 130 131
66 132 133
67 134 135
68 136 137
69 138 139
70 140 141
71 142 143
72 144 145
73 146 147
74 148 149
75 150 151
76 152 153
77 154 155
78 156 157
79 158 159
80 160 161
81 162 163
82 164 165
83 166 167
84 168 169
85 170 171
86 172 173
87 174 175
88 176 177
89 178 179
90 180 181
91 182 183
92 184 185
93 186 187
94 188 189
95 190 191
96 192 193
97 194 195
98 196 197
99 198 199
100 200 201
101 202 203
102 204 205
103 206 207
104 208 209
105 210 211
106 212 213
107 214 215
108 216 217
109 218 219
110 220 221
111 222 223
112 224 225
113 226 227
114 228 229
115 230 231
116 232 233
117 234 235
118 236 237
119 238 239
120 240 241
121 242 243
122 244 245
123 246 247
124 248 249
125 250 251
126 252 253
127 254 255
===============================

Iesire:

test 1:
2
---------------------
test 2:
1
----------------------
test 3:
1581130980
---------------------
test 4:
28710
---------------------
test 5:
148
-----------------
